{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Recover the Original Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #enumeration #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #枚举 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: recoverArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #还原原数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 有一个下标从 <strong>0</strong> 开始的数组 <code>arr</code> ，由 <code>n</code> 个正整数组成。她会选择一个任意的 <strong>正整数 </strong><code>k</code> 并按下述方式创建两个下标从 <strong>0</strong> 开始的新整数数组 <code>lower</code> 和 <code>higher</code> ：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>对每个满足 <code>0 &lt;= i &lt; n</code> 的下标 <code>i</code> ，<code>lower[i] = arr[i] - k</code></li>\n",
    "\t<li>对每个满足 <code>0 &lt;= i &lt; n</code> 的下标 <code>i</code> ，<code>higher[i] = arr[i] + k</code></li>\n",
    "</ol>\n",
    "\n",
    "<p>不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 <code>lower</code> 和 <code>higher</code> 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。</p>\n",
    "\n",
    "<p>给你一个由 2n 个整数组成的整数数组 <code>nums</code> ，其中 <strong>恰好</strong> <code>n</code> 个整数出现在 <code>lower</code> ，剩下的出现在 <code>higher</code> ，还原并返回 <strong>原数组</strong> <code>arr</code> 。如果出现答案不唯一的情况，返回 <strong>任一</strong> 有效数组。</p>\n",
    "\n",
    "<p><strong>注意：</strong>生成的测试用例保证存在 <strong>至少一个</strong> 有效数组 <code>arr</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,10,6,4,8,12]\n",
    "<strong>输出：</strong>[3,7,11]\n",
    "<strong>解释：</strong>\n",
    "如果 arr = [3,7,11] 且 k = 1 ，那么 lower = [2,6,10] 且 higher = [4,8,12] 。\n",
    "组合 lower 和 higher 得到 [2,6,10,4,8,12] ，这是 nums 的一个排列。\n",
    "另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下，lower = [2,4,6] 且 higher = [8,10,12] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,3,3]\n",
    "<strong>输出：</strong>[2,2]\n",
    "<strong>解释：</strong>\n",
    "如果 arr = [2,2] 且 k = 1 ，那么 lower = [1,1] 且 higher = [3,3] 。\n",
    "组合 lower 和 higher 得到 [1,1,3,3] ，这是 nums 的一个排列。\n",
    "注意，数组不能是 [1,3] ，因为在这种情况下，获得 [1,1,3,3] 唯一可行的方案是 k = 0 。\n",
    "这种方案是无效的，k 必须是一个正整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,435]\n",
    "<strong>输出：</strong>[220]\n",
    "<strong>解释：</strong>\n",
    "唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下，lower = [5] 且 higher = [435] 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 * n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>生成的测试用例保证存在 <strong>至少一个</strong> 有效数组 <code>arr</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [recover-the-original-array](https://leetcode.cn/problems/recover-the-original-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [recover-the-original-array](https://leetcode.cn/problems/recover-the-original-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,10,6,4,8,12]', '[1,1,3,3]', '[5,435]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        for j in range(1, len(nums)):\n",
    "            inh = [False] * len(nums)\n",
    "            inh[j] = True\n",
    "            dif = nums[j] - nums[0]\n",
    "            if dif == 0 or dif % 2 == 1:\n",
    "                continue\n",
    "            i = 0\n",
    "            nexti = i + 1\n",
    "            nextj = j + 1\n",
    "            cnt = 2\n",
    "            while nexti < len(nums):\n",
    "                while inh[nexti] and nexti + 1 < len(nums):\n",
    "                    nexti += 1\n",
    "                if not inh[nexti]:\n",
    "                    while nextj < len(nums) and nums[nextj] - nums[nexti] < dif:\n",
    "                        nextj += 1\n",
    "                    if nextj < len(nums) and nums[nextj] - nums[nexti] == dif:\n",
    "                        inh[nextj] = True\n",
    "                        cnt += 2\n",
    "                nexti += 1\n",
    "                nextj += 1                        \n",
    "            if cnt == len(nums):\n",
    "                res = []\n",
    "                for x in range(len(nums)):\n",
    "                    if inh[x]:\n",
    "                        res.append(nums[x] - dif // 2)\n",
    "                return res                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        for i in range(1,n//2+1):\n",
    "            d = nums[i]-nums[0]\n",
    "            if d==0 or d%2==1:continue\n",
    "            visited=[False]*n\n",
    "            visited[i]=True\n",
    "            res = [(nums[i]+nums[0])>>1]\n",
    "            lo,hi=1,i+1\n",
    "            while hi<n:\n",
    "                while lo<n and visited[lo]:\n",
    "                    lo+=1\n",
    "                while hi<n and nums[hi]-nums[lo]<d:\n",
    "                    hi+=1\n",
    "                if hi==n or nums[hi]-nums[lo]>d:\n",
    "                    break\n",
    "                visited[hi]=True\n",
    "                res.append((nums[lo]+nums[hi])>>1)\n",
    "                lo+=1\n",
    "                hi+=1\n",
    "            if len(res)==n//2:return res\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        length = len(nums)//2\n",
    "        def check(nums, k):\n",
    "            length = len(nums)//2\n",
    "            ans = []\n",
    "            d = deque()\n",
    "            i = 0\n",
    "            while (i < 2*length):\n",
    "                if d:\n",
    "                    temp = d.popleft()\n",
    "                else:\n",
    "                    temp = nums[i] + 2*k\n",
    "                    ans.append(nums[i]+k)\n",
    "                    i += 1\n",
    "                while (nums[i] < temp):\n",
    "                    ans.append(nums[i]+k)\n",
    "                    d.append(nums[i] + 2*k)\n",
    "                    i += 1\n",
    "                    if (i == 2*length):\n",
    "                        return []\n",
    "                if (nums[i] > temp) & (i < 2*length):\n",
    "                    return []\n",
    "                else:\n",
    "                    i += 1 \n",
    "            if d:\n",
    "                return []\n",
    "            else:\n",
    "                return ans\n",
    "        # return check(nums,1)\n",
    "        for i in range(1,length + 1):\n",
    "            if (nums[i]>nums[0]) & ((nums[i]-nums[0])%2 == 0):\n",
    "                k = (nums[i]-nums[0])//2\n",
    "                if check(nums,k) != []:\n",
    "                    return check(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        length = len(nums)//2\n",
    "        def check(nums, k):\n",
    "            length = len(nums)//2\n",
    "            ans = []\n",
    "            d = deque()\n",
    "            i = 0\n",
    "            while (i < 2*length):\n",
    "                if d:\n",
    "                    temp = d.popleft()\n",
    "                else:\n",
    "                    temp = nums[i] + 2*k\n",
    "                    ans.append(nums[i]+k)\n",
    "                    i += 1\n",
    "                while (nums[i] < temp):\n",
    "                    ans.append(nums[i]+k)\n",
    "                    d.append(nums[i] + 2*k)\n",
    "                    i += 1\n",
    "                    if (i == 2*length):\n",
    "                        return []\n",
    "                if (nums[i] > temp) & (i < 2*length):\n",
    "                    return []\n",
    "                else:\n",
    "                    i += 1 \n",
    "            if d:\n",
    "                return []\n",
    "            else:\n",
    "                return ans\n",
    "        # return check(nums,1)\n",
    "        for i in range(1,length + 1):\n",
    "            if (nums[i]>nums[0]) & ((nums[i]-nums[0])%2 == 0):\n",
    "                k = (nums[i]-nums[0])//2\n",
    "                if check(nums,k) != []:\n",
    "                    return check(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        nums.sort()\n",
    "        n0 = nums[0]\n",
    "        for i in range(1,N):\n",
    "            ni = nums[i]\n",
    "            if (ni-n0)&1 or ni==nums[i-1]:\n",
    "                continue\n",
    "            \n",
    "            used = [False]*N\n",
    "            used[0] = used[i] = True\n",
    "            k = (ni-n0)//2\n",
    "            \n",
    "            res = [n0+k]\n",
    "\n",
    "            l = 0\n",
    "            r = i\n",
    "            for _ in range(N//2-1):\n",
    "                while l<N and used[l]:\n",
    "                    l += 1\n",
    "                nr = nums[l]+k*2\n",
    "                while r<N and (used[r] or nums[r]<nr):\n",
    "                    r += 1\n",
    "                if r<N and nums[r] == nr:\n",
    "                    res.append(nums[l]+k)\n",
    "                    used[l] = used[r] = True\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        #print(nums)\n",
    "        for ph0 in range(1, n):\n",
    "            h0 = nums[ph0]\n",
    "            k = h0 - nums[0]\n",
    "            if k & 1: continue\n",
    "\n",
    "            ans = [(h0 + nums[0]) // 2]\n",
    "            vis = set()\n",
    "            vis.add(ph0)\n",
    "            i = 1\n",
    "            j = ph0 + 1\n",
    "            #print(k)\n",
    "            while j < n:\n",
    "                while i < n and i in vis: i += 1\n",
    "                if i == n: break\n",
    "                while j < n and nums[j] - nums[i] < k: j += 1\n",
    "                if j == n or nums[j] - nums[i] > k: break\n",
    "                #print(k, i, j)\n",
    "                vis.add(j)\n",
    "                ans.append((nums[j] + nums[i]) // 2)\n",
    "                i += 1\n",
    "                j += 1\n",
    "            #print(ans)\n",
    "            if len(ans) == n // 2: return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for i in range(1,len(nums)):\n",
    "            sum_ = abs(nums[0]-nums[i])\n",
    "            if sum_%2==0:\n",
    "                f = True\n",
    "                d = {}\n",
    "                for num in nums:\n",
    "                    if num in d:\n",
    "                        d[num] += 1\n",
    "                    else:\n",
    "                        d[num] = 1\n",
    "                res = []\n",
    "                for i in range(len(nums)):\n",
    "                    if nums[i] in d and d[nums[i]]>0:\n",
    "                        t = nums[i] + sum_\n",
    "                        if t in d and d[t] > 0:\n",
    "                            res.append(nums[i]+sum_//2)\n",
    "                            d[nums[i]] -= 1\n",
    "                            d[t] -= 1\n",
    "                        else:\n",
    "                            f = False\n",
    "                            break\n",
    "                if f:\n",
    "                    ans = res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, mid, cnt, nums):\n",
    "        pos = 0\n",
    "        ans = []\n",
    "        while pos < len(nums):\n",
    "            if len(nums) - pos < ((len(nums)//2) - len(ans)):\n",
    "                return [False, []]\n",
    "            if cnt[nums[pos]] > 0:\n",
    "                ans.append(nums[pos] + mid)\n",
    "                cnt[nums[pos]] -= 1\n",
    "                high = nums[pos] + 2 * mid\n",
    "                if high not in cnt or cnt[high] == 0:\n",
    "                    return [False, []]\n",
    "                cnt[high] -= 1\n",
    "            pos += 1\n",
    "        if len(ans) * 2 == len(nums):\n",
    "            return [True, ans]\n",
    "        else:\n",
    "            return [False, []]\n",
    "    \n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        cnt_all = Counter(nums)\n",
    "        for i in range((len(nums) // 2), 0, -1):\n",
    "            delta = nums[i] - nums[0]\n",
    "            if delta % 2 == 1:\n",
    "                continue\n",
    "            delta //= 2\n",
    "            test = self.check(delta, cnt_all.copy(), nums)\n",
    "            if test[0] == True:\n",
    "                return test[1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[0] or (nums[i] - nums[0]) % 2 !=0:\n",
    "                continue\n",
    "            \n",
    "            used = [False] * n\n",
    "            used[0] = used[i] =True\n",
    "            k = (nums[i] - nums[0]) // 2\n",
    "            \n",
    "            ans = [nums[0] + k]\n",
    "            left, right = 0, 1\n",
    "            for j in range(1, n//2):\n",
    "                while used[left]:\n",
    "                    left += 1\n",
    "                while right < n and (used[right] or nums[right] - nums[left] != k*2):\n",
    "                    right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "                ans.append(nums[left]+k)\n",
    "                used[left] = used[right] = True\n",
    "            if len(ans) == n // 2:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def fun(i):\n",
    "            k = (nums[i] - nums[0]) // 2\n",
    "            dic = Counter(nums)\n",
    "            dic[nums[0]] -= 1\n",
    "            dic[nums[i]] -= 1\n",
    "            res = [nums[0] + k]\n",
    "            for a in range(1, n):\n",
    "                if dic[nums[a]]:\n",
    "                    b = nums[a] + k*2\n",
    "                    if not dic[b]:\n",
    "                        return []\n",
    "                    dic[nums[a]] -= 1\n",
    "                    dic[b] -= 1\n",
    "                    res.append(b-k)\n",
    "            return res\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > nums[0] and not (nums[i] - nums[0]) % 2:\n",
    "                res = fun(i)\n",
    "                if res:\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, mid, cnt, nums):\n",
    "        pos = 0\n",
    "        ans = []\n",
    "        while pos < len(nums):\n",
    "            # if len(nums) - pos < ((len(nums)//2) - len(ans)):\n",
    "            #     return [False]\n",
    "            if cnt[nums[pos]] > 0:\n",
    "                ans.append(nums[pos] + mid)\n",
    "                cnt[nums[pos]] -= 1\n",
    "                high = nums[pos] + 2 * mid\n",
    "                if high not in cnt or cnt[high] == 0:\n",
    "                    return [False]\n",
    "                cnt[high] -= 1\n",
    "            pos += 1\n",
    "        if len(ans) * 2 == len(nums):\n",
    "            return [True, ans]\n",
    "        else:\n",
    "            return [False]\n",
    "    \n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        cnt_all = Counter(nums)\n",
    "        for i in range((len(nums) // 2), 0, -1):\n",
    "            delta = nums[i] - nums[0]\n",
    "            if delta % 2 == 1:\n",
    "                continue\n",
    "            delta //= 2\n",
    "            test = self.check(delta, cnt_all.copy(), nums)\n",
    "            if test[0] == True:\n",
    "                return test[1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[0] or (nums[i] - nums[0]) % 2 != 0:\n",
    "                continue\n",
    "            used = [False] * n\n",
    "            used[0] = used[i] = True\n",
    "            k = (nums[i] - nums[0]) // 2\n",
    "            ans = [nums[0] + k]\n",
    "            \n",
    "            left, right = 0, i\n",
    "            for j in range(1, n // 2):\n",
    "                while used[left]:\n",
    "                    left += 1\n",
    "                while right < n and (used[right] or nums[right] - nums[left] != k * 2):\n",
    "                    right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "                ans.append(nums[left] + k)\n",
    "                used[left] = used[right] = True\n",
    "            if len(ans)==n//2:\n",
    "                return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) >> 1\n",
    "        nums.sort()\n",
    "        delta = nums[n] - nums[0]\n",
    "        if delta & 1 == 0 and all(nums[off + n] - nums[off] == delta for off in range(1, n)):\n",
    "            delta >>= 1\n",
    "            for off in range(n):\n",
    "                nums[off] += delta\n",
    "            return nums[:n]\n",
    "        s = nums[0] + nums[-1]\n",
    "        r = n*2\n",
    "        n0 = nums[0]\n",
    "        q = deque()\n",
    "        result = [-1]*n\n",
    "        for l, nL in enumerate(nums[1:n], 1):\n",
    "            delta = nL - n0\n",
    "            if delta & 1: continue\n",
    "            nR = s - nL\n",
    "            r = bisect_right(nums, nR,l+1,r)\n",
    "            if nums[r - 1] != nR: continue\n",
    "            q.clear()\n",
    "            q.extend(nums[:l])\n",
    "            rOff = 0\n",
    "            for tempL in range(l, n*2):\n",
    "                nL = nums[tempL]\n",
    "                if not q:\n",
    "                    q.append(nL)\n",
    "                    continue\n",
    "                q0 = q[0] + delta\n",
    "                if nL > q0: break\n",
    "                if nL < q0:\n",
    "                    q.append(nL)\n",
    "                else:\n",
    "                    result[rOff] = q.popleft()\n",
    "                    rOff += 1\n",
    "            else:\n",
    "                if not q:\n",
    "                    delta >>= 1\n",
    "                    for i in range(n):\n",
    "                        result[i] += delta\n",
    "                    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, mid, cnt, nums):\n",
    "        pos = 0\n",
    "        ans = []\n",
    "        while pos < len(nums):\n",
    "            if len(nums) - pos < ((len(nums)//2) - len(ans)):\n",
    "                return [False]\n",
    "            if cnt[nums[pos]] > 0:\n",
    "                ans.append(nums[pos] + mid)\n",
    "                cnt[nums[pos]] -= 1\n",
    "                high = nums[pos] + 2 * mid\n",
    "                if high not in cnt or cnt[high] == 0:\n",
    "                    return [False]\n",
    "                cnt[high] -= 1\n",
    "            pos += 1\n",
    "        if len(ans) * 2 == len(nums):\n",
    "            return [True, ans]\n",
    "        else:\n",
    "            return [False]\n",
    "    \n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        cnt_all = Counter(nums)\n",
    "        for i in range((len(nums) // 2), 0, -1):\n",
    "            delta = nums[i] - nums[0]\n",
    "            if delta % 2 == 1:\n",
    "                continue\n",
    "            delta //= 2\n",
    "            test = self.check(delta, cnt_all.copy(), nums)\n",
    "            if test[0] == True:\n",
    "                return test[1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[0] or (nums[i] - nums[0]) % 2 != 0:\n",
    "                continue\n",
    "            \n",
    "            used = [False] * n\n",
    "            used[0] = used[i] = True\n",
    "            k = (nums[i] - nums[0]) // 2\n",
    "            ans = [nums[0] + k]\n",
    "            \n",
    "            left, right = 0, i\n",
    "            for j in range(1, n // 2):\n",
    "                while used[left]:\n",
    "                    left += 1\n",
    "                while right < n and (used[right] or nums[right] - nums[left] != k * 2):\n",
    "                    right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "                ans.append(nums[left] + k)\n",
    "                used[left] = used[right] = True\n",
    "            \n",
    "            if len(ans) == n // 2:\n",
    "                return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)//2\n",
    "        nums.sort()\n",
    "     \n",
    "        for i in range(2*n-1,-1,-1):\n",
    "            diff = nums[-1] - nums[i]\n",
    "\n",
    "            if diff & 1 or diff == 0:\n",
    "                continue\n",
    "            k = diff // 2\n",
    "            cnt = Counter(nums)\n",
    "            ans = []\n",
    "\n",
    "            for key in sorted(cnt.keys()):\n",
    "                if cnt[key + 2*k] < cnt[key]:\n",
    "                    break\n",
    "                ans.extend([key+k] * cnt[key])\n",
    "                cnt[key + 2*k] -= cnt[key]\n",
    "                cnt[key] = 0\n",
    "            if all(v==0 for v in cnt.values()):\n",
    "                return ans\n",
    "        return []\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, mid, cnt, nums):\n",
    "        pos = 0\n",
    "        ans = []\n",
    "        while pos < len(nums):\n",
    "            if cnt[nums[pos]] > 0:\n",
    "                ans.append(nums[pos] + mid)\n",
    "                cnt[nums[pos]] -= 1\n",
    "                high = nums[pos] + 2 * mid\n",
    "                if high not in cnt or cnt[high] == 0:\n",
    "                    return [False, []]\n",
    "                cnt[high] -= 1\n",
    "            pos += 1\n",
    "        if len(ans) * 2 == len(nums):\n",
    "            return [True, ans]\n",
    "        else:\n",
    "            return [False, []]\n",
    "    \n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        cnt_all = Counter(nums)\n",
    "        for i in range((len(nums) // 2), 0, -1):\n",
    "            delta = nums[i] - nums[0]\n",
    "            if delta % 2 == 1:\n",
    "                continue\n",
    "            delta //= 2\n",
    "            test = self.check(delta, cnt_all.copy(), nums)\n",
    "            if test[0] == True:\n",
    "                return test[1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[0] or (nums[i] - nums[0]) % 2 != 0:\n",
    "                continue\n",
    "            \n",
    "            used = [False] * n\n",
    "            used[0] = used[i] = True\n",
    "            k = (nums[i] - nums[0]) // 2\n",
    "            ans = [nums[0] + k]\n",
    "            \n",
    "            left, right = 0, i\n",
    "            for j in range(1, n // 2):\n",
    "                while used[left]:\n",
    "                    left += 1\n",
    "                while right < n and (used[right] or nums[right] - nums[left] != k * 2):\n",
    "                    right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "                ans.append(nums[left] + k)\n",
    "                used[left] = used[right] = True\n",
    "            \n",
    "            if len(ans) == n // 2:\n",
    "                return ans\n",
    "        \n",
    "        # 题目保证一定有解，不会到这一步\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        nums.sort()\n",
    "        n0 = nums[0]\n",
    "        for i in range(1,N):\n",
    "            ni = nums[i]\n",
    "            if ni == n0 or (ni-n0)&1:\n",
    "                continue\n",
    "            \n",
    "            used = [False]*N\n",
    "            used[0] = used[i] = True\n",
    "            k = (ni-n0)//2\n",
    "            \n",
    "            res = [n0+k]\n",
    "\n",
    "            l = 0\n",
    "            r = i\n",
    "            for _ in range(N//2-1):\n",
    "                while l<N and used[l]:\n",
    "                    l += 1\n",
    "                nl = nums[l]\n",
    "                nr = nl+k*2\n",
    "                while r<N and (used[r] or nums[r]-nl<k*2):\n",
    "                    r += 1\n",
    "                if r<N and nums[r] == nr:\n",
    "                    res.append(nl+k)\n",
    "                    used[l] = used[r] = True\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        nums.sort()\n",
    "        n0 = nums[0]\n",
    "        for i in range(1,N):\n",
    "            ni = nums[i]\n",
    "            if (ni-n0)&1 or ni==nums[i-1]:\n",
    "                continue\n",
    "            \n",
    "            used = [False]*N\n",
    "            used[0] = used[i] = True\n",
    "            k = (ni-n0)//2\n",
    "            \n",
    "            res = [n0+k]\n",
    "\n",
    "            l = 0\n",
    "            r = i\n",
    "            for _ in range(N//2-1):\n",
    "                while l<N and used[l]:\n",
    "                    l += 1\n",
    "                nl = nums[l]\n",
    "                nr = nl+k*2\n",
    "                while r<N and (used[r] or nums[r]-nl<k*2):\n",
    "                    r += 1\n",
    "                if r<N and nums[r] == nr:\n",
    "                    res.append(nl+k)\n",
    "                    used[l] = used[r] = True\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        length = len(nums)//2\n",
    "        def check(nums, k):\n",
    "            length = len(nums)//2\n",
    "            ans = []\n",
    "            d = deque()\n",
    "            i = 0\n",
    "            while (i < 2*length):\n",
    "                if d:\n",
    "                    temp = d.popleft()\n",
    "                else:\n",
    "                    temp = nums[i] + 2*k\n",
    "                    ans.append(nums[i]+k)\n",
    "                    i += 1\n",
    "                while (nums[i] < temp):\n",
    "                    ans.append(nums[i]+k)\n",
    "                    d.append(nums[i] + 2*k)\n",
    "                    i += 1\n",
    "                    if (i == 2*length):\n",
    "                        return []\n",
    "                if (nums[i] > temp) & (i < 2*length):\n",
    "                    return []\n",
    "                else:\n",
    "                    i += 1 \n",
    "            if d:\n",
    "                return []\n",
    "            else:\n",
    "                return ans\n",
    "        # return check(nums,1)\n",
    "        for i in range(1,length + 1):\n",
    "            if (nums[i]>nums[0]) & ((nums[i]-nums[0])%2 == 0):\n",
    "                k = (nums[i]-nums[0])//2\n",
    "                if check(nums,k) != []:\n",
    "                    return check(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        \n",
    "        def check():\n",
    "            cnt = Counter(nums)\n",
    "            res = []\n",
    "            for num in nums:\n",
    "                if cnt[num]:\n",
    "                    if cnt[num+2*k]:\n",
    "                        res.append(num+k)\n",
    "                        cnt[num+2*k] -= 1\n",
    "                        cnt[num] -= 1\n",
    "                    else:\n",
    "                        return []\n",
    "            return res\n",
    "        \n",
    "        n = len(nums)\n",
    "        start = nums[0]\n",
    "        for j in range(1, n):\n",
    "            end = nums[j]\n",
    "            if (end-start) % 2 == 0 and (end-start)//2 > 0:\n",
    "                k = (end-start)//2\n",
    "                cur = check()\n",
    "                if cur:\n",
    "                    return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        def dfs(length):\n",
    "            cnts[nums[0]] -= 1\n",
    "            cnts[nums[0] + length] -= 1\n",
    "            a , b = [nums[0]] , [nums[0]+length]\n",
    "            j = 0\n",
    "            while j < n:\n",
    "                while j < n and cnts[nums[j]] == 0:\n",
    "                    j += 1\n",
    "                if j == n:break\n",
    "                if cnts[nums[j]+length] == 0:return []\n",
    "                cnts[nums[j]] -= 1\n",
    "                cnts[nums[j]+length] -= 1\n",
    "                a += [nums[j]]\n",
    "                b += [nums[j]+length]\n",
    "            return [(a[i]+b[i])//2 for i in range(len(a))]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            length = nums[i] - nums[0]\n",
    "            if length % 2 == 1 or length == 0:continue\n",
    "            cnts = Counter(nums)\n",
    "            a = dfs(length)\n",
    "            if a:return a\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(1,n//2+1):\n",
    "            diff = nums[i]-nums[0]\n",
    "            if not diff or diff % 2:continue\n",
    "            flag = 1\n",
    "            Res = [(nums[0]+nums[i])//2]\n",
    "            C = Counter(nums)\n",
    "            C[nums[0]] -= 1;C[nums[i]] -= 1\n",
    "            for j in range(1,n):\n",
    "                if not C[nums[j]]:continue\n",
    "                if C[nums[j]+diff] > 0:\n",
    "                    C[nums[j]+diff] -= 1\n",
    "                    C[nums[j]] -= 1\n",
    "                    Res.append(nums[j]+diff//2)\n",
    "                else:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag:return Res\n",
    "\n",
    "# print(Solution().recoverArray([i+1 for i in range(1000)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\r\n",
    "        ans = []\r\n",
    "        nums.sort()\r\n",
    "        for i in range(1, len(nums)):\r\n",
    "            d = nums[i] - nums[0]\r\n",
    "            if d & 1 or d == 0:\r\n",
    "                continue\r\n",
    "            lq = Deque(nums[:i])\r\n",
    "            a = []\r\n",
    "            for j in range(i, len(nums)):\r\n",
    "                if lq and lq[0] + d == nums[j]:\r\n",
    "                    a.append(lq[0] + d // 2)\r\n",
    "                    lq.popleft()\r\n",
    "                else:\r\n",
    "                    lq.append(nums[j])\r\n",
    "            if not lq:\r\n",
    "                ans = a\r\n",
    "                break\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        length=len(nums)\n",
    "        max_k=(nums[length-1] - nums[length//2 -1])//2\n",
    "        counter_init=Counter(nums)\n",
    "        k_range=[]\n",
    "        for t in range(length//2 -1,length-1):\n",
    "            k_range.append((nums[length-1] - nums[t])//2)\n",
    "        # for k in range(max_k,0,-1):\n",
    "        for k in k_range:\n",
    "            flag=True\n",
    "            counter_init=Counter(nums)\n",
    "            counter=counter_init\n",
    "            # print(counter)\n",
    "            keys=counter.keys()\n",
    "            keys=list(keys)\n",
    "            for key in keys:\n",
    "                # print(key)\n",
    "                # if(counter[keys]==0):\n",
    "                #     continue\n",
    "                if(counter[key+2*k]<counter[key]):\n",
    "                    flag=False\n",
    "                    break\n",
    "                else:\n",
    "                    counter[key+2*k]-=counter[key]\n",
    "                    counter[key]=0\n",
    "            if(flag):\n",
    "                ans=[]\n",
    "                counter_init=Counter(nums)\n",
    "                counter=counter_init\n",
    "                # print(counter)\n",
    "                keys=counter.keys()\n",
    "                keys=list(keys)\n",
    "                for key in counter.keys():\n",
    "                    if(counter[key]==0):\n",
    "                        continue\n",
    "                    ans.extend([key+k]*counter[key])\n",
    "                    counter[key+2*k]-=counter[key]\n",
    "                    counter[key]=0\n",
    "                return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        def dfs(length):\n",
    "            cnts[nums[0]] -= 1\n",
    "            cnts[nums[0] + length] -= 1\n",
    "            a , b = [nums[0]] , [nums[0]+length]\n",
    "            while True:\n",
    "                j = 0\n",
    "                while j < n and cnts[nums[j]] == 0:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    break\n",
    "                if cnts[nums[j]+length] == 0:return []\n",
    "                cnts[nums[j]] -= 1\n",
    "                cnts[nums[j]+length] -= 1\n",
    "                a += [nums[j]]\n",
    "                b += [nums[j]+length]\n",
    "            return [(a[i]+b[i])//2 for i in range(len(a))]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            length = nums[i] - nums[0]\n",
    "            if length % 2 == 1 or length == 0:continue\n",
    "            cnts = Counter(nums)\n",
    "            a = dfs(length)\n",
    "            if a:return a\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        length=len(nums)\n",
    "        max_k=(nums[length-1] - nums[length//2 -1])//2\n",
    "        counter_init=Counter(nums)\n",
    "        k_range=[]\n",
    "        for t in range(length//2 -1,length-1):\n",
    "            k_range.append((nums[length-1] - nums[t])//2)\n",
    "        # for k in range(max_k,0,-1):\n",
    "        for k in k_range:\n",
    "            flag=True\n",
    "            counter_init=Counter(nums)\n",
    "            counter=counter_init\n",
    "            # print(counter)\n",
    "            keys=counter.keys()\n",
    "            keys=list(keys)\n",
    "            for key in keys:\n",
    "                # print(key)\n",
    "                # if(counter[keys]==0):\n",
    "                #     continue\n",
    "                if(counter[key+2*k]<counter[key]):\n",
    "                    flag=False\n",
    "                    break\n",
    "                else:\n",
    "                    counter[key+2*k]-=counter[key]\n",
    "                    counter[key]=0\n",
    "            if(flag):\n",
    "                ans=[]\n",
    "                counter_init=Counter(nums)\n",
    "                counter=counter_init\n",
    "                # print(counter)\n",
    "                keys=counter.keys()\n",
    "                keys=list(keys)\n",
    "                for key in counter.keys():\n",
    "                    if(counter[key]==0):\n",
    "                        continue\n",
    "                    ans.extend([key+k]*counter[key])\n",
    "                    counter[key+2*k]-=counter[key]\n",
    "                    counter[key]=0\n",
    "                return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
